#include "Heap.h"

/// Construtores e destrutor ///
Heap::Heap(size_t n,size_t t,int(*comparador)(const void*,const void*))
{
    // Checar se "n", "t" e "comparador" são válidos:
    if ((n != 0) && (t != 0) && (comparador != NULL))
    {
        // Tentar alocar espaço para o vetor interno do heap:
        vetor = new (nothrow) byte[n*t];
        // Checar se foi possível alocar a memória:
        if (vetor != NULL)
        {
            // Preencher o vetor com zeros:
            fill((byte*)vetor,(byte*)vetor+n,0);
            // Setar o resto dos atributos:
            tamanho_heap = 0;
            tamanho_maximo = n;
            tamanho_elemento = t;
            funcao_comparacao = comparador;
            return;
        }
    }
    // Caso algo dê errado, usamos o construtor padrão:
    this->inicializador();
}

Heap::Heap(void* v, size_t n, size_t t, int(*comparador)(const void*,const void*))
{
    // Checar se "v", "n", "t" e "comparador" são válidos:
    if ((v != NULL) && (n != 0) && (t != 0) && (comparador != NULL))
    {
        // Tentar alocar espaço para o vetor interno do heap:
        vetor = new (nothrow) byte[n*t];
        // Checar se foi possível alocar a memória:
        if (vetor != NULL)
        {
            // Copiar os elementos de "v" para "vetor":
            copy((byte*)v,(byte*)v+n*t,(byte*)vetor);
            // Setar o resto dos atributos:
            tamanho_heap = n;
            tamanho_maximo = n;
            tamanho_elemento = t;
            funcao_comparacao = comparador;
            return;
        }
    }
    // Caso algo dê errado, usamos o construtor padrão:
    this->inicializador();
}

// Construtor-cópia:
Heap::Heap(const Heap& h)
{
    if (h.tamanho_maximo != 0)
    {
        // Tentar alocar espaço para o vetor interno do heap:
        vetor = new (nothrow) byte[h.tamanho_maximo*h.tamanho_elemento];
        // Checar se foi possível alocar a memória:
        if (vetor != NULL)
        {
            // Copiar os elementos de "h" para "this":
            copy(
                (byte*)h.vetor,
                (byte*)h.vetor+h.tamanho_maximo*h.tamanho_elemento,
                (byte*)(this->vetor)
                );
            // Setar o resto dos atributos:
            this->tamanho_heap      = h.tamanho_heap;
            this->tamanho_maximo    = h.tamanho_maximo;
            this->tamanho_elemento  = h.tamanho_elemento;
            this->funcao_comparacao = h.funcao_comparacao;
            return;
        }
    }
    // Caso algo dê errado, usamos o construtor padrão:
    this->inicializador();
}

Heap::~Heap()
{
    delete[] (byte*)vetor;
}

/// Métodos privados ///
void Heap::inicializador()
{
    vetor = NULL;
    tamanho_heap = 0;
    tamanho_maximo = 0;
    tamanho_elemento = 0;
    funcao_comparacao = NULL;
}

void* Heap::get(size_t posicao)
{
    if (posicao >= tamanho_maximo) return(NULL);
    return((byte*)vetor+tamanho_elemento*posicao);
}

void Heap::trocar(size_t primeiro, size_t segundo)
{
    if(primeiro == segundo) return;
    if(primeiro >= tamanho_maximo) return;
    if(segundo  >= tamanho_maximo) return;

    byte* a   = (byte*)get(primeiro);
    byte* b   = (byte*)get(segundo);
    byte* aux = new byte[tamanho_elemento];

    /// Usar memcpy() equivale a usar:
    /// for(size_t i=0 ; i<tamanho_elemento ; i++) aux[i] = a[i];

    /// aux = a:
    memcpy(aux,a,tamanho_elemento);
    /// a = b:
    memcpy(a,b,tamanho_elemento);
    /// b = aux:
    memcpy(b,aux,tamanho_elemento);

    delete[] aux;
}

size_t Heap::pai(size_t i)
{
    if(i==0) return(0);
    return((i-1)>>1);
}

size_t Heap::filho_esquerdo(size_t i)
{
    return((i<<1)+1);
}

size_t Heap::filho_direito(size_t i)
{
    return((i<<1)+2);
}

size_t Heap::heapup(size_t i)
{
    /**
    Caso o valor de "i" dado seja maior ou igual ao valor do tamanho máximo do vetor interno do heap,
    retornamos o valor de "tamanho_maximo" para indicar que "i" está fora dos limites do vetor.
    Os valores permitidos para "tamanho_maximo" são [0,tamanho_maximo-1].
    **/
    if(i >= tamanho_maximo) return(tamanho_maximo);

    size_t pi = pai(i);

    //cout<<"i = "<<i<<endl;
    /// Enquanto (i > 0) E (vetor[i] <= vetor[pi]) faça:
    while((i > 0) && (funcao_comparacao(get(i),get(pi)) > 0))
    {
        /// vetor[i] <=> vetor[pi]:
        trocar(i,pi);
        i = pi;
        pi = pai(i);
        //cout<<"i = "<<i<<endl;
    }

    return(i);
}

size_t Heap::heapdown(size_t i)
{
    /** Veja a explicação para a linha abaixo na função "heapup" **/
    if(i >= tamanho_maximo) return(tamanho_maximo);

    size_t esq,dir,menor;

    while(true)
    {
        esq = filho_esquerdo(i);
        dir = filho_direito(i);

        /// Se (esq < tamanho_heap) E (vetor[esq] <= vetor[i]) então:
        if((esq < tamanho_heap) && (funcao_comparacao(get(esq),get(i)) > 0))
            menor = esq;
        else
            menor = i;

        /// Se (dir < tamanho_heap) E (vetor[dir] <= vetor[menor]) então:
        if((dir < tamanho_heap) && (funcao_comparacao(get(dir),get(menor)) > 0))
            menor = dir;

        if(i == menor)
            break;
        else
        {
            /// vetor[i] <=> vetor[menor]
            trocar(i,menor);
            i = menor;
        }
    }

    return(i);
}

/// Métodos públicos ///
void trocar_atributos(Heap& pri, Heap& seg)
{
    swap(pri.vetor            ,seg.vetor);
    swap(pri.tamanho_heap     ,seg.tamanho_heap);
    swap(pri.tamanho_maximo   ,seg.tamanho_maximo);
    swap(pri.tamanho_elemento ,seg.tamanho_elemento);
    swap(pri.funcao_comparacao,seg.funcao_comparacao);
}

Heap& Heap::operator=(Heap h)
{
    trocar_atributos(*this,h);
    return(*this);
}

size_t Heap::tamanho() const
{
    return(tamanho_heap);
}

size_t Heap::tamanhoMax() const
{
    return(tamanho_maximo);
}

void Heap::heapify()
{
    for(size_t i=pai(tamanho_heap) ; i>0 ; i--) heapdown(i);
    heapdown(0);
}

void Heap::heapoffer(void *x)
{
    if(tamanho_heap < tamanho_maximo)
    {
        /// vetor[tamanho_heap] = x:
        memcpy(get(tamanho_heap),x,tamanho_elemento);
        heapup(tamanho_heap);
        tamanho_heap++;
    }
}

void* Heap::heappoll()
{
    if(tamanho_heap)
    {
        tamanho_heap--;
        // O elemento da raiz do heap será trocado com o da última posição:
        trocar(0,tamanho_heap);
        heapdown(0);
        // Retornamos uma referência ao elemento da raiz do heap
        // (só que agora ele está na última posição, pois foi removido do heap):
        return(get(tamanho_heap));
    }
    return(NULL);
}

void* Heap::heapsort()
{
    if(this->tamanho_maximo == 0) return(NULL);

    // Organizar os elementos do vetor interno na forma de um heap:
    this->heapify();

    // Salvar tamanho atual do heap:
    size_t tam_heap = this->tamanho_heap;

    // Loop que usa a função "heappoll()" repetidas vezes para remover o
    // elemento da raiz do heap. Como esta função o copia para a última posição
    // do vetor interno, no final teremos os elementos ordenados no próprio
    // vetor interno do heap:
    while(heappoll());

    // Ao final dos vários "heappoll()" o tamanho atual do heap será setado para zero.
    // Aqui restauramos o valor inicial:
    this->tamanho_heap = tam_heap;

    // Retornar uma referência para o vetor interno do heap:
    return(vetor);
}
